package CommonAlgs.sort;

import java.util.Arrays;
import java.util.Scanner;

public class QuickSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        quicksort(a, 0, n - 1);
        System.out.println(Arrays.toString(a));
    }

    private static void quicksort(int[] a, int left, int right) {
        if (left > right) return;
        int i = left;
        int j = right;
        int base = a[left]; //基准数
        while (i != j) {
            while (a[j] >= base && i < j) j--;
            while (a[i] <= base && i < j) i++;
            //交换两个数在数组中的位置
            if (i < j) { //ij没有相遇
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
        //ij相遇，交换base元素与i所在元素
        a[left] = a[i];
        a[i] = base;
        quicksort(a, left, i - 1); //继续处理左边的序列
        quicksort(a, i + 1, right); //继续处理右边的序列
    }


}
